The invention relates to processing algorithms involving Galois Field arithmetic and relates particularly, though not exclusively, to the efficient execution of algorithms involving Galois Field arithmetic, as typically found in communications and cryptography applications.
A Galois Field is a finite set of elements in which addition, subtraction, multiplication and division (all appropriately defined) can be performed without leaving the set. Addition and multiplication must satisfy the commutative, associative and distributive laws. Galois Field arithmetic finds wide use in a variety of engineering applications, including error correcting codes and cryptography. For a concise and comprehensive exposition of Galois Fields, refer to Lidl and Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, Mass., 1986.
In view of the varied applications noted above, there has been considerable attention given to efficient methods and apparatuses for Galois Field computations. In this respect, U.S. Pat. No. 5,689,452 issued to Cameron on Nov. 18, 1997 discloses a programmable digital computer with special-purpose logic units to efficiently perform Galois Field arithmetic. Cameron discloses a method of decoding Reed-Solomon codes in a large Galois Field GF(2n) in which the finite field is represented as a quadratic extension field of one or more subfields GF(2m). Basic arithmetic operations in the extension field are written solely in terms of operations performed in one or more subfields. Multiplicative operations performed in GF(2n) use only operations from GF(2m).
There have also been attempts to efficiently perform Galois Field arithmetic on general-purpose wide-word computers. A wide-word computer with a W-bit word can be looked upon as a SIMD (single instruction, multiple data) computer capable of operating upon one or more sets of k operands, each (W/k) bits wide, simultaneously with a common instruction. Computers with such architectures can be used to efficiently perform several computations in parallel and, accordingly, there are potential efficiency advantages that may be exploited. However, existing SIMD architectures are not ideally suited to performing Galois Field arithmetic as such architectures are not able to effectively perform operations typically associated with data manipulations executed when computing Galois Field operations.
Despite the work referred to above, there are limitations associated with existing techniques. Accordingly, a need clearly exists for a method . . . at least attempt to address these and other limitations associated with such techniques.
It is recognised that efficient parallel processing of algorithms involving Galois Field arithmetic can be achieved using an appropriate decomposition into corresponding operations in selected subfields.
Accordingly, a first aspect of the invention provides a method for processing algorithms involving Galois Field arithmetic suitable for execution by digital hardware able to process k-bit operands. This involves mapping source arithmetic operations in Galois Field GF(2n) into respective sets of corresponding arithmetic operations for a plurality of isomorphic composite Galois Fields GF((2p[1])p[2]) . . . )p[v]), for each of which xcfx80vi=1p[i]=n.
For each respective set of corresponding operations, a cost function relating to an implementation of the source arithmetic operations with the set of corresponding arithmetic operations is evaluated. As a result, one of the sets of corresponding arithmetic operations is selected as a target set of arithmetic operations, based on the calculated results of the cost function for each of the respective sets. Further, the source arithmetic operations of Galois Field GF(2n) are converted to the target set of arithmetic operations of the respective isomorphic composite Galois Field, the target arithmetic operations having k-bit operands.
In the described embodiment, the technique of data-slicing is used in combination with the mathematical technique of mapping arithmetic operations of the field GF(2n) in terms of operations in appropriately chosen subfields of GF(2n). Described embodiments enable Galois Field arithmetic to be effectively executed with SIMD computing architectures with relative efficiency and speed. An efficient implementation for any algorithm with Galois Field arithmetic can be derived where significant data-parallelism exists. Two examples of such an algorithm are Reed-Solomon decoders (generally described in Lin and Costello, Error Control Coding, Prentice Hall; ISBN: 013283796X, October 1982), and the recently selected Rijndael proposal for private key (symmetric key) cryptography.
Though there are advantages associated with implementing the described method with a data-sliced arrangement, such methods can also be executed on existing SIMD or non-SIMD architectures. The described methods are not restricted to the preferred Galois Field computer hardware architecture described herein, though there is a clear performance benefit available as the efficiency of the method depends on the architecture used.
The aspects of the invention attempt to provide an efficient implementation of applications involving Galois Field arithmetic in which there is the potential to exploit data parallelism with by performing relevant calculations with relatively greater computational efficiency.